Bresenham's Algorithm

The Bresenham algorithm is a way of computing which cells are intersected by a line using only integer arithmetic.

Bresenham developed this algorithm to draw lines in a graphics environment. It is simple, fast and can show which pixels need to be illuminated on a screen to plot a particular line. In our case, the screen is our grid map and the pixels are nodes or grid cells. Because we're using this algorithm for collision detection instead of illuminating pixels, we'll implement it in a slightly different way.

Your goal here is to figure out how to get from p_1 = (x_1, y_1) to p_2 = (x_2, y_2) by starting at p_1 and moving 1 unit in the x or y direction until you arrive at p_2. Whether you decide to move vertically or horizontally is determined by your current position with respect to the line connecting p_1 and p_2. For example, moving from the point (0, 0) to (7, 5) would look like this:

The difference between this method and the typical computer graphics implementation is that in computer graphics, it's about drawing lines with pixels rather than collision detection so the cells illuminated end up missing some potential collisions along the way from p_1 to p_2.

There's a Python package called Bresenham that uses the computer graphics method. We can use this package and run the same process of identifying the cells that lie along a line from (0, 0) to (7, 5) as we did above and you'll see that the result looks a bit different:

With this second method, there are cells the line crosses that are not identified in the plot and this is because the restriction of only being able to move one step in either x or y is not imposed here. In other words, diagonal motions are allowed in the computer graphics version of this drawing method.

What that means is that if you're using the graphics method, you could potentially miss some cells that are in collision if you're planning a trajectory that flies close to obstacles. This is probably fine if you've padded obstacles with a safety margin in creation of your grid map.

Bresenham Exercise

In this exercise, you'll get a chance to both implement your own version of Bresenham's algorithm as well as play with the Python Bresenham package implementation. The reason for doing both is that sometimes just using the prebuilt version is fine, but you also need to understand how it can impact your planning solution and how to modify the algorithm to suit your needs if necessary.

To keep things relatively simple, in the notebook below you'll implement a method for detecting cells that are in collision with a line from points p_1 = (x_1, y_1) and p_2 = (x_2, y_2), where x_1 < x_2 and y_1 < y_2. Extending this method to work with any p_1 and p_2 is left as an extra challenge to you!

After that you'll have a chance to play around with the package implementation of Bresenham's algorithm. Follow along with the TODOs in the notebook below and if you get stuck, you can check out our solution by scrolling down to the link at the bottom of the notebook.